package offer.tree;

import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-03-01 20:35
 */
public class n_37 {
    public static void main(String[] args) {
        n_37 n = new n_37();
        TreeNode t1 = new TreeNode(8);
        TreeNode t2 = new TreeNode(6);
        TreeNode t3 = new TreeNode(10);
        TreeNode t4 = new TreeNode(5);
        TreeNode t5 = new TreeNode(7);
        TreeNode t6 = new TreeNode(9);
        TreeNode t7 = new TreeNode(11);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
        t3.right = t7;
        n.inOrder(t1);
        //8!6!5!#!#!7!#!#!10!9!#!#!11!#!#
        String res = n.Serialize(t1);
        System.out.println(res);
//        TreeNode node = n.Deserialize(res);
//        System.out.println(node);

    }

    String Serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        return root.val + "!" + Serialize(root.left) + "!" + Serialize(root.right);
    }


    String origin = null;

    TreeNode Deserialize(String str) {
        if (str.length() == 0) {
            return null;
        }
        origin = str;
        int idx = origin.indexOf("!");
        String value = idx == -1 ? origin.substring(0, 1) : origin.substring(0, idx);
        origin = idx == -1 ? origin.substring(0) : origin.substring(idx + 1);
        if (value.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = Deserialize(origin);
        node.right = Deserialize(origin);
        return node;
    }

    void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode cur = node;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
            cur = pop.right;
        }
    }

}


